#include<vector>
#include<unordered_set>
#include<deque>
#include<string>
using namespace std;
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        string start = "0000";
        unordered_set<string>deadend_set;
        unordered_set<string>visited;
        for (string str : deadends)
            deadend_set.insert(str);
        if (deadend_set.find(target) != deadend_set.end() ||
            deadend_set.find(start) != deadend_set.end())
            return -1;
        if (start == target)
            return 0;
        deque<string>queue;
        visited.insert(start);
        queue.push_back(start);
        int num = 0;
        int action[2] = { -1,1 };
        while (!queue.empty()) {
            int size = queue.size();
            while (size > 0) {
                --size;
                string str = queue.front();
                queue.pop_front();
                for (int i = 0; i < 4; ++i) {
                    char tmp = str[i];
                    for (int j = 0; j < 2; ++j) {
                        str[i] = ((tmp - '0') + 10 + action[j]) % 10 + '0';
                        if (target == str)
                            return  num + 1;
                        if (deadend_set.find(str) == deadend_set.end() &&
                            visited.find(str) == visited.end()) {
                            queue.push_back(str);
                            visited.insert(str);
                        }
                    }
                    str[i] = tmp;
                }
            }
            ++num;
        }
        return -1;
    }
};